/**
 * 斐波那契数列
 * int fib(int N) {
    if (N == 1 || N == 2) return 1;
    return fib(N - 1) + fib(N - 2);
    }
 */

 // 自顶而下，耗时最长，因为有重复计算浪费
// function fib(N) { // 执行时间：1.142ms
//     if (N == 1 || N == 2) return 1;
//     return fib(N - 1) + fib(N - 2);
// }

//建一个帮助函数，额外存储计算过的值。
// function fib(N) { // 执行时间：0.094ms
//     var arr = [];
//     var helper = function (i) {
//         if (i == 1 || i == 2) return 1;
//         if (arr[i] !== undefined) {
//             return arr[i];
//         }
//         var temp = helper(i - 1) + helper(i - 2);
//         arr[i] = temp;
//         return temp;
//     };
//     return helper(N);
// }

//从下往上算
function fib(N) { // 执行时间：0.103ms
    if (N == 1 || N == 2) return 1;
    var pre = fib(1);
    var cur = fib(2);
    for (let i = 3; i <= N; i++) {
        var sum = pre + cur; // 第3个
        pre = cur; // 第2个变成前一个
        cur = sum; // 第3个变成当前的
    }
    return cur;
}

console.time('fib');
var res = fib(20); // 6765
console.timeEnd('fib');
console.log(res);